\(
\newcommand{\water}{{\rm H_{2}O}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\d}{\mathop{}\!\mathrm{d}}
\newcommand{\grad}{\nabla}
\newcommand{\T}{^\text{T}}
\newcommand{\mathbbone}{\unicode{x1D7D9}}
\renewcommand{\:}{\enspace}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\Tr}{Tr}
\newcommand{\norm}[1]{\lVert #1\rVert}
\newcommand{\KL}[2]{ \text{KL}\left(\left.\rule{0pt}{10pt} #1 \; \right\| \; #2 \right) }
\newcommand{\slashfrac}[2]{\left.#1\middle/#2\right.}
\)
Let \(\; X_1, X_2, \ldots \;\) be a homogeneous Markov chain with values on a finite state space \(\; D \;\) and transition probability matrix \(\; P = (p_{ij}), \: i, j \in D \;\). \(\; P \;\) determines whether the sequence can go from any state \(\; i \;\) to any other state \(\; j \;\) in a single step, and more generally \(\; P^{n} \;\) tells us whether a path exists from a state \(\; i \;\) to another state \(\; j \;\) in \(\; n \;\) steps. We denote the existence of a path between \(\; i \;\) and \(\; j \;\) as \(\; i \rightsquigarrow j \;\), and the lack of a path as \(\; i \not\rightsquigarrow j \;\)
-
A state \(\; i \;\) is called transient if it is eventually abandoned, never to return to it again. This is because there exists at least one state \(\; j \;\) for which there are outward paths, \(\; i \rightsquigarrow j \;\), but there are no returning paths, \(\; j \not\rightsquigarrow i \;\), so the chain will eventually move away from \(\; i \;\) forever.
-
A state \(\; i \;\) is called recurrent if it is forever visited over and over again, infinite times. This is because for every outward path \(\; i \rightsquigarrow j \;\) there exists a returning path \(\; j \not\rightsquigarrow i \;\), so the chain will always eventually come back sooner or later.
-
If a recurrent state \(\; i \;\) has a path towards another state \(\; j \;\), then \(\; j \;\) must also be recurrent (or else there would be trajectories that would take the Markov chain away from both states forever, making both of them transient).
-
Similarly, if a state \(\; i \;\) has a path towards a transient state \(\; j \;\), then \(\; i \;\) must also be transient (since the second state has trajectories that take the Markov chain away forever).
Therefore, the state space \(\; D \;\) can be partitioned into distinct regions of interconnected states that are all either recurrent or all transient. Each of the recurrent regions is called a recurrence class.